// 2025/5/22
// 最少的完全平方数

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    int n; cin >> n;
    int num = sqrt(n);
    vector<vector<int>> bag(num + 1, vector<int>(n + 1, n));
    for (int i = 0; i <= num; i++)
        bag[i][0] = 0;

    for (int i = 1; i <= num; i++)
    {
        int tmp = i * i;
        for (int j = 1; j <= n; j++)
        {
            bag[i][j] = bag[i - 1][j];
            if (j >= tmp)
            {
                bag[i][j] = min(bag[i][j], bag[i - 1][j - tmp] + 1);
                bag[i][j] = min(bag[i][j], bag[i][j - tmp] + 1);
            }
        }
    }
    cout << bag[num][n] << endl;
}
// 64 位输出请用 printf("%lld")